package com.alex.algorithm.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    public static void main(String[] args) {
        List<ArrayList<Integer>> threeSumList = threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        threeSumList.stream().forEach(l -> l.stream().forEach(i -> System.out.println(i)));
    }

    private static List<ArrayList<Integer>> threeSum(int[] array) {
        Arrays.sort(array);
        List<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < array.length; ++i) {
            int left = i;
            int right = array.length - 1;
            if (i > 0 && array[i] == array[i - 1]) continue;
            while(left < right) {
                int sum = array[i] + array[left] + array[right];
                if(left == i) {
                    ++left;
                }else if(right == i) { // todo
                    --right;
                }else if (sum == 0) {
                    ArrayList<Integer> threeSum = new ArrayList<>();
                    threeSum.add(array[i]);
                    threeSum.add(array[left]);
                    threeSum.add(array[right]);
                    list.add(threeSum);
                    while (array[left] == array[left + 1]) {
                        ++left;
                    }
                    ++left;
                    while (array[right] == array[right - 1]) {
                        --right;
                    }
                    --right;
                    continue;
                }else if (sum < 0){
                    left++;
                }else {
                    right--;
                }

            }
        }
        return list;
    }
}
